<!DOCTYPE html>
<html>
  <head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#33363b">
    <meta name="msapplication-TileColor" content="#33363b">
    
    
    
    
    <meta name="keywords" content="GCU, ACM, Algorithm">
    
    
    <link rel="apple-touch-icon" sizes="180x180" href="/favicons/apple-touch-icon.png">
    
    
    <link rel="icon" type="image/png" sizes="192x192" href="/favicons/android-chrome-192x192.png">
    
    
    <link rel="icon" type="image/png" sizes="32x32" href="/favicons/favicon-32x32.png">
    
    
    <link rel="icon" type="image/png" sizes="16x16" href="/favicons/favicon-16x16.png">
    
    
    <link rel="mask-icon" href="/favicons/safari-pinned-tab.svg" color="#33363b">
    
    
    <link rel="manifest" href="/favicons/site.webmanifest">
    
    
    <meta name="msapplication-config" content="/favicons/browserconfig.xml">
    
    
    <link rel="alternate" href="/atom.xml" title="GCU-ACM" type="application/atom+xml">
    
    
    <link rel="shortcut icon" type="image/x-icon" href="/favicons/favicon.ico">
    
    
    <link rel="stylesheet" type="text/css" href="/css/normalize.css">
    <link rel="stylesheet" type="text/css" href="/css/index.css">
    
    <link rel="stylesheet" type="text/css" href="/css/sidebar.css">
    
    
<link rel="stylesheet" type="text/css" href="/css/page.css">
<link rel="stylesheet" type="text/css" href="/css/post.css">

    <link rel="stylesheet" type="text/css" href="/css/custom.css">
    <link rel="stylesheet" type="text/css" href="/css/atom-one-dark.css">
    <link rel="stylesheet" type="text/css" href="/css/lightgallery.min.css">
    <script type="text/javascript" src="/js/jquery.min.js"></script>
    <script defer type="text/javascript" src="/js/util.js"></script>
    <script defer type="text/javascript" src="/js/clipboard.min.js"></script>
    <script defer type="text/javascript" src="/js/scrollspy.js"></script>
    <script defer type="text/javascript" src="/js/fontawesome-all.min.js"></script>
    <script defer type="text/javascript" src="/js/lightgallery.min.js"></script>
    <script defer type="text/javascript" src="/js/lg-fullscreen.min.js"></script>
    <script defer type="text/javascript" src="/js/lg-hash.min.js"></script>
    <script defer type="text/javascript" src="/js/lg-pager.min.js"></script>
    <script defer type="text/javascript" src="/js/lg-thumbnail.min.js"></script>
    <script defer type="text/javascript" src="/js/lg-zoom.min.js"></script>
    
    <script defer src="/js/busuanzi.pure.mini.js"></script>
    
    
    <script defer type="text/javascript" src="/js/search.js"></script>
    <script type="text/javascript">
    $(document).ready(function () {
      var searchPath = "search.xml";
      if (searchPath.length === 0) {
        searchPath = "search.xml";
      }
      var path = "/" + searchPath;
      searchFunc(path, "search-input", "search-result");
    });
    </script>
    
    
    
    <script defer type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
    <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ["$","$"], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ["script", "noscript", "style", "textarea", "pre", "code"]
      }
    });
    </script>
    <script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for (i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += " has-jax";
      }
    });
    </script>
    
    
    <script defer type="text/javascript" src="/js/index.js"></script>
    <script type="text/javascript">
    $(document).ready(function () {
      var cb = null;
      var els = $(".post figure.highlight");
      if (els.length) {
        // Enabled Hexo highlight line number.
        $(els).each(function (i, e) {
          $(e).before("<button class=\"copy button\">複製</button>");
        });
        cb = new ClipboardJS("button.copy", {
          "target": function (trigger) {
              // Get target element by DOM API.
              // nextElementSibling is figure,highlight.
              // And following is the sequence of Hexo's internal
              // highlight layout with line number.
              return trigger.nextElementSibling.firstChild.firstChild.firstChild.lastChild.firstChild.firstChild;
          }
        });
      } else {
        // Disabled Hexo highlight line number.
        els = $(".post pre code");
        $(els).each(function (i, e) {
          // Add button before pre, not code.
          $(e).parent().before("<button class=\"copy button\">複製</button>");
        });
        cb = new ClipboardJS("button.copy", {
          "target": function (trigger) {
              // Get target element by DOM API.
              // nextElementSibling is figure,highlight.
              // And following is the sequence of Hexo's internal
              // highlight layout without line number.
              return trigger.nextElementSibling.firstChild;
          }
        });
      }
      cb.on("success", function (e) {
        e.clearSelection();
        var trigger = e.trigger;
        // Change button text as a user tip.
        trigger.innerHTML = "已複製";
        $(trigger).addClass("copied");
        // Change button text back;
        setTimeout(function () {
          trigger.innerHTML = "複製";
          $(trigger).removeClass("copied");
        }, 1500);
      });
    });
    </script>
    
    <script defer type="text/javascript" src="/js/custom.js"></script>
    <title>LCS&&LIS | GCU-ACM - Talk is cheap,show me your code</title>
  </head>
  <body itemscope itemtype="http://schema.org/WebPage" lang="zh_CN" data-spy="scroll" data-target=".list-group">
    
<header id="header" class="header" style="background: #33363b;">
  <div class="container">
    <div class="header-container">
      <div class="header-title">
        <h1 class="title"><a href="/">GCU-ACM</a></h1>
        <h2 class="subtitle">Talk is cheap,show me your code</h2>
      </div>
      
      <div class="logo">
        <img src="/images/logo.png" alt="logo">
      </div>
      
    </div>
    <nav id="nav" class="nav">
      <a id="nav-toggle" class="nav-toggle" aria-hidden="true"><i class="fas fa-bars" aria-label="切换导航栏"></i></a>
      <ul id="menu" role="menubar" aria-hidden="false">
        
        <li role="menuitem"><a href="/"><i class="fas fa-home"></i><span class="menu-text">首页</span></a></li>
        
        <li role="menuitem"><a href="/archives/"><i class="fas fa-archive"></i><span class="menu-text">归档</span></a></li>
        
        <li role="menuitem"><a href="/categories/"><i class="fas fa-th-list"></i><span class="menu-text">分类</span></a></li>
        
        <li role="menuitem"><a href="/tags/"><i class="fas fa-tags"></i><span class="menu-text">标签</span></a></li>
        
        <li role="menuitem"><a href="/about/"><i class="fas fa-user-edit"></i><span class="menu-text">关于</span></a></li>
        
        <li role="menuitem"><a href="http://gcuacm.gitee.io/new2018"><i class="far fa-hand-rock"></i><span class="menu-text">招新</span></a></li>
        
      </ul>
    </nav>
  </div>
</header>


    <main id="main" class="main">
      <div class="container">
        <div class="main-container">
          <div class="content">
            
<div id="post" class="page">
  
  <article class="article post card" itemscope itemtype="http://schema.org/Article">
    <div class="post-block">
      <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/04/04/190404/">
      <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
       <meta itemprop="name" content="码到成功">
       <meta itemprop="description" content="除非你能在床上赚钱，否则就不要赖在床上">
       <meta itemprop="image" content="/images/avatar.png">
      </span>
      <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
       <meta itemprop="name" content="GCU-ACM">
      </span>
    </div>
    <header class="post-header">
      <h1 class="post-title" itemprop="name headline">LCS&&LIS</h1>
      <div class="post-meta">
        
        <span class="post-date">
          <i class="far fa-calendar-plus"></i><span><time title="post-date" itemprop="dateCreated datePublished" datetime="2019-04-04T15:49:44+08:00">2019-04-04 15:49:44</time></span>
        </span>
        
        
        
        <span class="post-meta-divider divider">|</span>
        
        <span class="post-categories">
          
          <i class="far fa-folder-open"></i><span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/教学/" itemprop="url" rel="index"><span itemprop="name">教学</span></a></span>
        </span>
        
        
        
        
      </div>
    </header>
    <main class="post-main" itemprop="articleBody">
      <p>最长公共子序列&amp;&amp;最长递增子序列</p>
<hr>
<p>作者：肖锐</p>
<a id="more"></a>
<h1 id="LCS—最长公共子序列"><a href="#LCS—最长公共子序列" class="headerlink" title="LCS—最长公共子序列"></a>LCS—最长公共子序列</h1><p><img src="/2019/04/04/190404/1.jpeg" alt><br><small>最长公共子序列不需要连续</small></p>
<hr>
<p>给定序列<br>s1={3,5,7,4,8,6,7,8,2}<br>s2={1,3,4,5,6,7,7,8}<br>s1和s2的相同子序列，且该子序列的长度最长，即是LCS<br>s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}</p>
<h2 id="动态规划法求LCS"><a href="#动态规划法求LCS" class="headerlink" title="动态规划法求LCS"></a>动态规划法求LCS</h2><p> 动态规划算法通常用于求解具有某种==最优性质==的问题。<br> 在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有==最优值==的解<br> 例如LCS中的‘最长’</p>
<h2 id="动态规划法的基本思路"><a href="#动态规划法的基本思路" class="headerlink" title="动态规划法的基本思路"></a>动态规划法的基本思路</h2><ol>
<li>动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。</li>
<li>若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。</li>
<li>如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算</li>
<li>将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策。换句话说，每个状态都是过去历史的一个完整总结，这就是无后效性<br><hr><br>三个特点：最优子结构、重叠子问题、无后效性</li>
</ol>
<h2 id="递归求斐波那契数列"><a href="#递归求斐波那契数列" class="headerlink" title="递归求斐波那契数列"></a>递归求斐波那契数列</h2><p>数列：1、1、2、3、5、8、13、21、34、……<br><figure class="hljs highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">f</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span><br></span>&#123;<br>    <span class="hljs-keyword">if</span>(n == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>    <span class="hljs-keyword">if</span>(n == <span class="hljs-number">1</span> ) <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">if</span>(n &gt;= <span class="hljs-number">2</span>)<br>    &#123;<br>        <span class="hljs-keyword">return</span> f(n<span class="hljs-number">-1</span>)+f(n<span class="hljs-number">-2</span>);<br>    &#125;<br>&#125;<br></code></pre></td></tr></table></figure></p>
<p>这种算法并不高效,它做了很多重复计算,它的时间复杂度为$O(2^n)​$</p>
<p><img src="/2019/04/04/190404/2.png" alt><br>在斐波拉契数列，可以看到大量的重叠子问题，比如说在求<code>fib(6)</code>的时候，<code>fib(2)</code>被调用了5次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。</p>
<h2 id="动规求斐波那契数列"><a href="#动规求斐波那契数列" class="headerlink" title="动规求斐波那契数列"></a>动规求斐波那契数列</h2><p>使用动态规划来将重复计算的结果具有”记忆性”,就可以将时间复杂度降低为O(n)<br><figure class="hljs highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">f</span><span class="hljs-params">()</span><br></span>&#123;<br>    <span class="hljs-keyword">int</span> f[<span class="hljs-number">10</span>];<br>    f[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>;<br>    f[<span class="hljs-number">1</span>] = <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">2</span>; i &lt;= <span class="hljs-number">10</span>; i++)<br>        f[i] = f[i<span class="hljs-number">-1</span>] + f[i<span class="hljs-number">-2</span>];<br>&#125;<br></code></pre></td></tr></table></figure></p>
<p><img src="/2019/04/04/190404/3.png" alt="100"></p>
<h2 id="回到原题，求解LCS"><a href="#回到原题，求解LCS" class="headerlink" title="回到原题，求解LCS"></a>回到原题，求解LCS</h2><p><big>解决LCS问题，需要把原问题分解成若干个子问题，所以需要刻画LCS的特征</big><br>设S1={A0,A1, … ,Am}，S2={B0,B1, … Bn}，它们LCS为Z={Z1,Z2, … ,Zk}</p>
<ol>
<li>如果Am=Bn，则Zk=Am=Bn，且{Z1, Z2, …, z(K-1)}是{A0,A1, … ,A(m-1)}和{B0,B1, … B(n-1)}的一个最长公共子序列<br><br><br><img src="/2019/04/04/190404/5.png" alt></li>
</ol>
<p>即假如S1的最后一个元素 与S2的最后一个元素相等，那么S1和S2的LCS就等于 <font color="red">{S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS  再加上 S1和S2相等的最后一个元素</font></p>
<hr>
<p>设S1={A0,A1, … ,Am}，S2={B0,B1, … Bn}，它们LCS为Z={Z1,Z2, … ,Zk}</p>
<ol start="2">
<li><p>如果Am!=Bn</p>
<ul>
<li>若Zk!=Am，则{Z1,Z2, … ,Zk}是{A0,A1, … ,A(m-1)}和{B0,B1, … Bn}的一个最长公共子序列</li>
<li><p>若Zk!=Bn，则{Z1,Z2, … ,Zk}是{A0,A1, … ,Am}和{B0,B1, … B(n-1)}的一个最长公共子序列</p>
<p>  <img src="/2019/04/04/190404/6.png" alt></p>
</li>
</ul>
</li>
</ol>
<p>假如S1的最后一个元素 与 S2的最后一个元素不等，那么S1和S2的LCS就等于 ： <font color="red">MAX( {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS)</font></p>
<h2 id="动态转移方程"><a href="#动态转移方程" class="headerlink" title="动态转移方程"></a>动态转移方程</h2><p>假设我们用C[i,j]表示Xi 和 Yj 的LCS的长度（直接保存最长公共子序列的中间结果不现实，需要先借助LCS的长度）。其中X = {x1 … xm}，Y ={y1…yn}，Xi = {x1 … xi}，Yj={y1… yj}。<br>可得动态转移方程如下：<br><img src="/2019/04/04/190404/7.jpeg" alt></p>
<hr>
<p>s1={1,3,4,5,6,7,7,8}，s2={3,5,7,4,8,6,7,8,2}<br><img src="/2019/04/04/190404/8.jpeg" alt><br>图中的空白格子需要填上相应的数字（这个数字就是C[i,j]的定义，记录的LCS的长度值）。填的规则依据公式，简单来说：如果横竖（i,j）对应的两个元素相等，该格子的值 = c[i-1,j-1] + 1。如果不等，取c[i-1,j] 和 c[i,j-1]的最大值。</p>
<hr>
<p>首先初始化该表。<br><img src="/2019/04/04/190404/9.jpeg" alt></p>
<hr>
<p>当i=2，j=1时，S1的元素3 与 S2的元素3 相等，所以 C[2,1] = C[1,0] + 1<br><img src="/2019/04/04/190404/11.jpeg" alt></p>
<hr>
<p>当i=2，j=2时，S1的元素3 与 S2的元素5 不等，C[2,2] =max(C[1,2],C[2,1])<br>图中C[1,2] 和 C[2,1] 背景色为浅黄色。<br><img src="/2019/04/04/190404/10.jpeg" alt> </p>
<hr>
<p><img src="/2019/04/04/190404/12.jpeg" alt><br>根据性质，c[8,9] = S1 和 S2 的 LCS的长度，即为5</p>
<h2 id="模板题–POJ1458-Common-Subsequence"><a href="#模板题–POJ1458-Common-Subsequence" class="headerlink" title="模板题–POJ1458(Common Subsequence)"></a>模板题–<a href="http://poj.org/problem?id=1458" target="_blank" rel="noopener">POJ1458(Common Subsequence)</a></h2><p><img src="/2019/04/04/190404/7.png" alt="80%"><br>题意：输入不定行，每行两个字符串，求每一行两个字符串的最长公共子序列长度</p>
<hr>
<figure class="hljs highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> MAXDP = <span class="hljs-number">1e3</span>;<br><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> MAXS = <span class="hljs-number">1e7</span>;<br><span class="hljs-keyword">int</span> dp[MAXDP][MAXDP];<br><span class="hljs-keyword">char</span> s1[MAXS], s2[MAXS];<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">LCS</span><span class="hljs-params">(<span class="hljs-keyword">char</span>* s1, <span class="hljs-keyword">char</span>* s2)</span><br></span>&#123;<br>    <span class="hljs-keyword">int</span> len1 = <span class="hljs-built_in">strlen</span>(s1) - <span class="hljs-number">1</span>;<span class="hljs-comment">//因为s1,s2是从1开始存的，所以长度要减1</span><br>    <span class="hljs-keyword">int</span> len2 = <span class="hljs-built_in">strlen</span>(s2) - <span class="hljs-number">1</span>;<br>    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;= len1; i++)<br>        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;= len2; j++)<br>        &#123;<br>            <span class="hljs-keyword">if</span>(i == <span class="hljs-number">0</span> || j == <span class="hljs-number">0</span>)	<br>            	dp[i][j] = <span class="hljs-number">0</span>;<br>            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(s1[i] == s2[j])<br>                dp[i][j] = dp[i - <span class="hljs-number">1</span>][j - <span class="hljs-number">1</span>] + <span class="hljs-number">1</span>;<br>            <span class="hljs-keyword">else</span><br>                dp[i][j] = max(dp[i - <span class="hljs-number">1</span>][j], dp[i][j - <span class="hljs-number">1</span>]);<br>        &#125;<br>        <span class="hljs-keyword">return</span> dp[len1][len2];<br>&#125;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span><br></span>&#123;<br>    s1[<span class="hljs-number">0</span>] = <span class="hljs-string">' '</span>, s2[<span class="hljs-number">0</span>] = <span class="hljs-string">' '</span>;<br>    <span class="hljs-keyword">while</span>(<span class="hljs-built_in">cin</span> &gt;&gt; s1 +<span class="hljs-number">1</span> &gt;&gt; s2 + <span class="hljs-number">1</span>)<br>        <span class="hljs-built_in">cout</span> &lt;&lt; LCS(s1, s2) &lt;&lt; <span class="hljs-built_in">endl</span>;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125; <span class="hljs-comment">//时间复杂度：O（len1*len2)</span><br></code></pre></td></tr></table></figure>
<h2 id="LCS进阶"><a href="#LCS进阶" class="headerlink" title="LCS进阶"></a>LCS进阶</h2><ol>
<li>还原最长公共子序列、记录路径：<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1503" target="_blank" rel="noopener">HDU1503(Advanced Fruits)</a></li>
<li>LCS变形：<ul>
<li><a href="http://poj.org/problem?id=1080" target="_blank" rel="noopener">POJ1080(Human Gene Functions)</a></li>
<li><a href="http://poj.org/problem?id=3356" target="_blank" rel="noopener">POJ3356(AGTC)</a></li>
</ul>
</li>
<li><a href="http://poj.org/problem?id=1159" target="_blank" rel="noopener">poj 1159 Palindrome LCS一维滚动数组优化</a></li>
</ol>
<hr>
<h1 id="最长公共子串（连续）"><a href="#最长公共子串（连续）" class="headerlink" title="最长公共子串（连续）"></a>最长公共子串（连续）</h1><p>和LCS区别是区别就是因为是连续的，如果两个元素不等，那么就要=0了而不能用之前一个状态的最大元素</p>
<p><img src="/2019/04/04/190404/8.png" alt> </p>
<p><img src="/2019/04/04/190404/7.jpeg" alt></p>
<hr>
<h1 id="LIS–最长递增子序列"><a href="#LIS–最长递增子序列" class="headerlink" title="LIS–最长递增子序列"></a>LIS–最长递增子序列</h1><p>假设有序列A = {5, 2, 8, 6, 3, 6, 9, 7}<br>其递增子序列有：{5,8,9}, {2,6,9}, {5,6,7}……<br>其中，最长递增子序列为{2, 3, 6, 9}和{2, 3, 6, 7}</p>
<h2 id="动态规划求LIS"><a href="#动态规划求LIS" class="headerlink" title="动态规划求LIS"></a>动态规划求LIS</h2><p>设dp[i]表示以i结尾的子序列中LIS的长度，dp[j] (0&lt;= j &lt; i) 来表示在i之前的LIS的长度<br>有一序列A={5, 3, 4, 8, 6, 7}</p>
<p><img src="/2019/04/04/190404/8.jpg" alt></p>
<h2 id="进一步分析"><a href="#进一步分析" class="headerlink" title="进一步分析"></a>进一步分析</h2><p>d(i) = max{ 1, d(j)+1} ,且满足A[i] &gt;= A[j]</p>
<ol>
<li>max显然是为了找到最长的满足条件的序列，容易理解</li>
<li>在max里面加入1作为比较的一员，是因为，最坏的情况就是序列是单调递减的，那么每个数都可以算是一个子序列，一个数的长度当然为1</li>
<li>d[j]为什么要加1呢，因为比较的数A[i] &gt; A[j]，那么A[i]就是最长子序列的一员，所以直接在d[j]上加1</li>
</ol>
<h2 id="模板题–HDU1257-最少拦截系统"><a href="#模板题–HDU1257-最少拦截系统" class="headerlink" title="模板题–HDU1257-最少拦截系统"></a><a href="http://acm.hdu.edu.cn/showproblem.php?pid=1257" target="_blank" rel="noopener">模板题–HDU1257-最少拦截系统</a></h2><p><img src="/2019/04/04/190404/9.png" alt></p>
<h2 id="解题"><a href="#解题" class="headerlink" title="解题"></a>解题</h2><p>我们所求的拦截系统的数目其实就是一个序列的所有递减子序列，并使其数量尽量减少，然后递减子序列的数目又会等于最长上升子序列中所含元素的个数；不理解的话可以去看下下面的test</p>
<figure class="hljs highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><code class="hljs c++">Input<br><span class="hljs-number">8</span> <span class="hljs-number">389</span> <span class="hljs-number">207</span> <span class="hljs-number">155</span> <span class="hljs-number">300</span> <span class="hljs-number">299</span> <span class="hljs-number">170</span> <span class="hljs-number">158</span> <span class="hljs-number">65</span><br><span class="hljs-number">1</span> <span class="hljs-number">100</span><br><span class="hljs-number">6</span> <span class="hljs-number">300</span> <span class="hljs-number">200</span> <span class="hljs-number">400</span> <span class="hljs-number">200</span> <span class="hljs-number">100</span> <span class="hljs-number">500</span><br><span class="hljs-number">8</span> <span class="hljs-number">500</span> <span class="hljs-number">300</span> <span class="hljs-number">400</span> <span class="hljs-number">200</span> <span class="hljs-number">300</span> <span class="hljs-number">100</span> <span class="hljs-number">200</span> <span class="hljs-number">50</span><br><span class="hljs-number">8</span> <span class="hljs-number">500</span> <span class="hljs-number">300</span> <span class="hljs-number">400</span> <span class="hljs-number">200</span> <span class="hljs-number">80</span> <span class="hljs-number">200</span> <span class="hljs-number">100</span> <span class="hljs-number">50</span><br><span class="hljs-number">8</span> <span class="hljs-number">500</span> <span class="hljs-number">300</span> <span class="hljs-number">400</span> <span class="hljs-number">200</span> <span class="hljs-number">80</span> <span class="hljs-number">500</span> <span class="hljs-number">100</span> <span class="hljs-number">50</span><br>Output<br><span class="hljs-number">213223</span><br></code></pre></td></tr></table></figure>
<figure class="hljs highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><code class="hljs c++"><span class="hljs-keyword">int</span> dp[<span class="hljs-number">100000</span>], arr[<span class="hljs-number">100000</span>], len;<br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">LIS</span><span class="hljs-params">()</span><br></span>&#123;<br>    <span class="hljs-built_in">memset</span>(dp, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(dp));<br>	<span class="hljs-keyword">int</span> MAX = <span class="hljs-number">-1e9</span>;<br>	<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= len; i++)<br>		<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; i; j++)<br>        &#123;<br>			<span class="hljs-keyword">if</span>(arr[i] &gt; arr[j] &amp;&amp; dp[i] &lt; dp[j] + <span class="hljs-number">1</span>)<br>			&#123;<br>				dp[i] = dp[j] + <span class="hljs-number">1</span>;<br>				<span class="hljs-keyword">if</span>(dp[i] &gt; MAX)<br>					MAX = dp[i];<br>			&#125;<br>        &#125;<br>	<span class="hljs-keyword">return</span> MAX;<br>&#125;<br><br><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;<br>	<span class="hljs-keyword">while</span>(<span class="hljs-built_in">cin</span> &gt;&gt; len)<br>    &#123;<br>		<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= len; i++)<br>			<span class="hljs-built_in">cin</span> &gt;&gt; arr[i];<br>		<span class="hljs-built_in">cout</span> &lt;&lt; LIS() &lt;&lt; <span class="hljs-built_in">endl</span>;<br>	&#125;<br>    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;<br>&#125;<span class="hljs-comment">//时间复杂度:O(n^2)</span><br></code></pre></td></tr></table></figure>
<h2 id="LIS进阶"><a href="#LIS进阶" class="headerlink" title="LIS进阶"></a>LIS进阶</h2><ol>
<li><p>算法优化：NlogN时间复杂度–可参考(20:41开始)</p>
<p><a href="https://www.bilibili.com/video/av18339080?from=search&amp;seid=11934838010834623209" target="_blank" rel="noopener">HRBU ACM 01背包 LIS 拓扑 凸包—-bilibili</a></p>
</li>
<li><p>最大递增子数组和–由LIS O(n2)的办法变化而来的，对应的模板题：</p>
<p><a href="http://acm.hdu.edu.cn/showproblem.php?pid=1087" target="_blank" rel="noopener">HDU1087(Super Jumping! Jumping! Jumping!)</a></p>
</li>
<li><p>LIS变形：</p>
<ul>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=5256" target="_blank" rel="noopener">HDU5256-序列变换</a></li>
<li><a href="https://www.luogu.org/problemnew/show/P1091" target="_blank" rel="noopener">洛谷P1091–合唱队形</a></li>
</ul>
</li>
</ol>

    </main>
    <footer class="post-footer">
      
      <div class="post-tags">
        
        <a class="post-tag button" href="/tags/LCS/" rel="tag"><i class="fas fa-tags"></i>LCS</a>
        
        <a class="post-tag button" href="/tags/LIS/" rel="tag"><i class="fas fa-tags"></i>LIS</a>
        
        <a class="post-tag button" href="/tags/dp/" rel="tag"><i class="fas fa-tags"></i>dp</a>
        
      </div>
      
    </footer>
  </article>
  
  
  <nav class="page-nav">
    <div class="page-nav-next page-nav-item">
      
      <a href="/2019/03/18/190318/" rel="next" title="扩展欧几里得算法与丢番图方程"><i class="fas fa-angle-left"></i><span class="nav-title">扩展欧几里得算法与丢番图方程</span></a>
      
    </div>
    <div class="page-nav-prev page-nav-item">
      
      <a href="/2019/04/08/190408/" rel="prev" title="2019测试赛I"><span class="nav-title">2019测试赛I</span><i class="fas fa-angle-right"></i></a>
      
    </div>
  </nav>
  
  
  

<div class="comments" id="comments">
  
  
  <div id="vcomments" class="vcomments"></div>
  <script defer src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script defer src="//unpkg.com/valine/dist/Valine.min.js"></script>
  <script type="text/javascript">
  $(document).ready(function () {
    new Valine({
      "el": "#vcomments",
      "appId": "9X1ViI1Sxnb7PFU97Od7SyUu-gzGzoHsz",
      "appKey": "FElrWSPz5YJXJ0PvokRFJDyu",
      "verify": "true",
      "notify": "true",
      "avatar": "mp",
      "meta": ["nick", "mail", "link"],
      "pageSize": 10,
      "lang": "zh-cn",
      "visitor": "false",
      "highlight": "true",
      "placeholder": "😎看了这么多，不想说点什么嘛😉(如果留有邮箱，当被回复时可收到邮件提醒哦)",
      "avatarForce": "false"
    });
  });
  </script>
  
  
</div>



  
</div>

          </div>
          
          
          
<aside class="sidebar" id="sidebar" style="background: url(/images/background.png);">
  
  <div class="search">
    <div class="form-group">
      <i class="fas fa-search"></i><input type="search" id="search-input" name="q" results="0" placeholder="搜索" class="form-control">
    </div>
  </div>
  <div class="search-result-box" id="search-result"></div>
  
  
<div class="info sidebar-item" id="info">
  
  <img class="author-avatar" src="/images/avatar.png" alt="码到成功">
  
  <h1 class="author-name">码到成功</h1>
  <h2 class="author-description">除非你能在床上赚钱，否则就不要赖在床上</h2>
  <div class="site-count">
    
    
    
    
    <div class="archives-count count-block">
      <div class="site-count-title">归档</div>
      <div><a href="/archives/">25</a></div>
    </div>
    
    
    
    <div class="categories-count count-block">
      <div class="site-count-title">分类</div>
      <div><a href="/categories/">4</a></div>
    </div>
    
    
    
    <div class="tags-count count-block">
      <div class="site-count-title">标签</div>
      <div><a href="/tags/">26</a></div>
    </div>
    
    
    
    
    
    
  </div>
  
  <div class="rss">
    <a class="rss-link button sidebar-item" href="/atom.xml"><i class="fas fa-rss"></i>RSS</a>
  </div>
  
</div>


  <div class="sidebar-sticky">
    
    
    
    
    
    <hr>
    <div class="post-toc sidebar-item" id="toc-div">
      <div><i class="fas fa-list-ol"></i>文章目录</div>
      <div class="post-toc-content"><ol class="list-group toc"><li class="toc-item toc-level-1"><a class="list-group-item toc-link" href="#LCS—最长公共子序列"><span class="toc-text">LCS—最长公共子序列</span></a><ol class="list-group toc-child"><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#动态规划法求LCS"><span class="toc-text">动态规划法求LCS</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#动态规划法的基本思路"><span class="toc-text">动态规划法的基本思路</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#递归求斐波那契数列"><span class="toc-text">递归求斐波那契数列</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#动规求斐波那契数列"><span class="toc-text">动规求斐波那契数列</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#回到原题，求解LCS"><span class="toc-text">回到原题，求解LCS</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#动态转移方程"><span class="toc-text">动态转移方程</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#模板题–POJ1458-Common-Subsequence"><span class="toc-text">模板题–POJ1458(Common Subsequence)</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#LCS进阶"><span class="toc-text">LCS进阶</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="list-group-item toc-link" href="#最长公共子串（连续）"><span class="toc-text">最长公共子串（连续）</span></a></li><li class="toc-item toc-level-1"><a class="list-group-item toc-link" href="#LIS–最长递增子序列"><span class="toc-text">LIS–最长递增子序列</span></a><ol class="list-group toc-child"><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#动态规划求LIS"><span class="toc-text">动态规划求LIS</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#进一步分析"><span class="toc-text">进一步分析</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#模板题–HDU1257-最少拦截系统"><span class="toc-text">模板题–HDU1257-最少拦截系统</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#解题"><span class="toc-text">解题</span></a></li><li class="toc-item toc-level-2"><a class="list-group-item toc-link" href="#LIS进阶"><span class="toc-text">LIS进阶</span></a></li></ol></li></ol></div>
    </div>
    
    
    
    <hr>
    <div class="social-link sidebar-item">
      <div><i class="far fa-address-card"></i>社交链接<p></p></div>
      <ul>
        
        <li><i class="fas fa-envelope"></i><a href="mailto:1239776759@qq.com" target="_blank">E-Mail</a></li>
        
      </ul>
    </div>
    
    
    <hr>
    <div class="blogroll sidebar-item">
      <div><i class="fas fa-link"></i>友情链接</div>
      <ul>
        
        <li><i class="fas fa-link"></i><a href="https://oi-wiki.org/" target="_blank">oi-wiki</a></li>
        
        <li><i class="fas fa-link"></i><a href="https://ac.nowcoder.com/acm/contest/vip-index" target="_blank">牛客竞赛</a></li>
        
        <li><i class="fas fa-link"></i><a href="http://fzcoj.hustoj.com" target="_blank">FZCOJ</a></li>
        
        <li><i class="fas fa-link"></i><a href="https://vjudge.net/article/187" target="_blank">kuangbin带你飞</a></li>
        
        <li><i class="fas fa-link"></i><a href="http://exp-blog.com/2018/06/28/pid-38/" target="_blank">POJ试题分类</a></li>
        
        <li><i class="fas fa-link"></i><a href="https://blog.csdn.net/hbhszxyb/article/details/19845559" target="_blank">OJ(Online Judge)系统及ACM测试题库大全</a></li>
        
      </ul>
    </div>
    
  </div>
</aside>


          
        </div>
      </div>
    </main>
    
<footer id="footer" class="footer" style="background: #33363b;">
  <div class="container">
    <div class="back-to-top">
      <button id="back-to-top"><i class="fas fa-angle-double-up" aria-label="回到顶部"></i></button>
    </div>
    <div class="footer-container">
      <div class="footer-left">
        <div class="copyright">
          <span class="author">码到成功</span><span class="year"><i class="far fa-copyright"></i>2020</span>
        </div>
        
        <div class="busuanzi">
          <span id="busuanzi_container_site_pv"><i class="fas fa-eye" aria-label="站点点击量" aria-hidden="false"></i><span id="busuanzi_value_site_pv"></span></span><span id="busuanzi_container_site_uv"><i class="fas fa-user" aria-label="站点用户数" aria-hidden="false"></i><span id="busuanzi_value_site_uv"></span></span><span id="busuanzi_container_page_pv"><i class="far fa-file-alt"></i><span id="busuanzi_value_page_pv" aria-label="页面点击量" aria-hidden="false"></span></span>
        </div>
        
      </div>
      <div class="footer-right">
        <div class="custom-info">
          
          托管于<i class="fab fa-github-alt"></i><a href="https://gitee.com/help/articles/4136" target="_blank">Gitee Pages</a>
          
        </div>
        <div class="powered-by">
          由 <a href="https://hexo.io/" target="_blank">Hexo</a> 强力驱动 | 主题 <a href="https://github.com/AlynxZhou/hexo-theme-aria/" target="_blank">ARIA</a>
        </div>
      </div>
    </div>
  </div>
</footer>


  </body>
</html>
